package madixin.t684;

import java.util.Arrays;

class Solution {
    private int[] parent;
    private int[] sz;

    //并查集
    public int[] findRedundantConnection(int[][] edges) {
        parent = new int[edges.length + 1];
        sz = new int[edges.length + 1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        Arrays.fill(sz, 1);

        int res[] = new int[2];
        for (int i = 0; i < edges.length; i++) {
            int m = edges[i][0];
            int n = edges[i][1];
            int pm = FindParent(m);
            int pn = FindParent(n);
            if (pm == pn) {
                res[0] = m;
                res[1] = n;
            } else {
                connect(pm, pn);
            }
        }

        return res;
    }

    private void connect(int pm, int pn) {
        if (sz[pm] > sz[pn]) {
            parent[pm] = pn;
            sz[pn] += sz[pm];
        } else {
            parent[pn] = pm;
            sz[pm] += sz[pn];
        }
    }

    private int FindParent(int i) {
        int p = parent[i];
        while (p != i) {
            i = p;
            p = parent[i];
        }
        return p;
    }
}